//1351. 统计有序矩阵中的负数
//思路：因为行列都是按非递增的排列
//所以从右上角开始判断，如果右上角是负数，那么这一列就都是负数
//如果不是，就往下跳一行，列位置不变，行往下是因为本行最后一个数都不是负数，前面的数字都不是
//所以另起一行，从最后继续观察


#include <vector>
using namespace std;

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        // int m = grid.size()-1, n = grid[0].size();
        // int count = 0, i = 0, tmp = m;
        // while(i < m)
        // {
        //     for(int j = 0; j < n; j++)
        //     {
        //         if(grid[i][j] < 0) count++;
        //         if(grid[m][j] < 0) count++;
        //     }
        //     i++;
        //     m--;
        // }
        // if(0 == tmp) count /= 2;
        // if(tmp % 2 == 0)
        // {
        //     for(int j = 0; j < n; j++)
        //     {
        //         if(grid[m][j] < 0) count++;
        //     }
        // }
        // return count;


        int count = 0;
        for(int i = 0, j = grid[0].size(); i < grid.size(), j >= 0; )
        {
            if(grid[i][j] >= 0)
            {
                i++;
            }
            else
            {
                count += grid.size() - i;
                j--;
            }
        }
        return count;
    }
};
